package basic.sort.tree;

import java.util.Stack;

/**
 * @author distantstar
 * @version 1.0
 * @date 2021
 * @description basic.sort.tree
 * @since JDK1.8
 */
public class BasicErgodicIteration {

    private static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int v) {
            value = v;
        }
    }

    private static void pre(Node node) {
        if (node == null) {
            return;
        }

        // 辅助栈
        Stack<Node> stack = new Stack<>();
        // 这里先添加头结点
        stack.add(node);

        // 弹出顶层节点，输出其值
        // 依次循环添加顶层节点的右子节点和左子节点
        while (!stack.isEmpty()) {
            Node temp = stack.pop();
            System.out.print(temp.value + " ");
            if (temp.right != null) {
                stack.add(temp.right);
            }
            if (temp.left != null) {
                stack.add(temp.left);
            }
        }
    }

    private static void med(Node node) {
        if (node == null) {
            return;
        }

        Stack<Node> stack = new Stack<>();
        Node temp = node;

        while (!stack.isEmpty() || temp != null) {
            // 判断当前节点是否为空
            // 不为空则添加该节点，并将该节点变成其左子节点
            if (temp != null) {
                stack.push(temp);
                temp = temp.left;
            } else {
                // 为空则证明当前节点的父节点的左子树已经遍历完成
                // 则弹出栈顶节点，输出其值，然后变成其右子节点
                temp = stack.pop();
                System.out.print(temp.value + " ");
                temp = temp.right;
            }
        }
    }

    private static void pos(Node node) {
        if (node == null) {
            return;
        }

        Stack<Node> stack = new Stack<>();
        Stack<Node> outputStack = new Stack<>();
        stack.add(node);

        Node temp;
        while (!stack.isEmpty()) {
            temp = stack.pop();
            outputStack.push(temp);

            if (temp.left != null) {
                stack.push(temp.left);
            }
            if (temp.right != null) {
                stack.push(temp.right);
            }
        }

        while (!outputStack.isEmpty()) {
            System.out.print(outputStack.pop().value + " ");
        }
    }

    private static void posOneStack(Node head) {
        if (head != null) {
            Stack<Node> stack = new Stack<>();
            stack.push(head);
            Node temp;

            while (!stack.isEmpty()) {
                temp = stack.peek();

                if (temp.left != null && head != temp.left && head != temp.right) {
                    stack.push(temp.left);
                } else if (temp.right != null && head != temp.right) {
                    stack.push(temp.right);
                } else {
                    System.out.print(stack.pop().value + " ");
                    head = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        head.left = new Node(2);
        head.right = new Node(3);
        head.left.left = new Node(4);
        head.left.right = new Node(5);
        head.right.left = new Node(6);
        head.right.right = new Node(7);

        pre(head);
        System.out.println("\n========");
        med(head);
        System.out.println("\n========");
        pos(head);
        System.out.println("\n========");
        posOneStack(head);
    }
}
